/*
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
 */
public class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length>nums2.length){
            int[] temp=nums1;
            nums1=nums2;
            nums2=temp;
        }
        if (nums1.length+nums2.length==1){
            return nums2[0];
        }
        int totalLeft=(nums1.length+nums2.length+1)/2;
        int l=0,r=nums1.length;
        while (l<r){
            int mid=(l+r+1)/2;
            int j=totalLeft-mid;
            if (nums1[mid-1]>nums2[j]){
                r=mid-1;
            }else{
                l=mid;
            }
        }
        int i=l,j=totalLeft-l;
        int leftMax;
        if (i==0){
            leftMax=nums2[j-1];
        }else if (j==0){
            leftMax=nums1[i-1];
        }else{
            leftMax=Math.max(nums1[i-1],nums2[j-1]);
        }
        int rightMax;
        if (i==nums1.length){
            rightMax=nums2[j];
        }else if (j==nums2.length){
            rightMax=nums1[i];
        }else{
            rightMax=Math.min(nums1[i],nums2[j]);
        }
        if ((nums1.length+nums2.length)%2==1){
            return leftMax;
        }else{
            return (1.0*leftMax+rightMax)/2;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution4().findMedianSortedArrays(new int[]{1,3},new int[]{2,7}));
    }
}
